The present invention relates to an image processing unit for performing an arithmetic operation between a reference image and a search image. Description of the Related Art Hitherto, there is known an apparatus for continuously tracking an object moving in a picture plane photographed by a television camera or a video camera. Such an apparatus for tracking a moving object is widely applicable to the fields as set forth below, for example:
(1) visualization of movement measurement and movement vector of non-contact
(2) automation of monitor and observation
(3) automatic recognition of gesture, expression and one""s eyes
(4) camera control of movie photography and sport relay broadcasting
(5) control of mobile robot and autonomic traveling car
In the event that the above-mentioned apparatus is used to recognize a position of a moving object, there is adopted a scheme that a pattern, which is the same as a pattern represented by a reference image or the similar pattern to the pattern represented by the reference image, is searched from a search image. For determination as to whether the pattern is identical or similar, there is often used an arithmetic method referred to as a correlation arithmetic operation.
FIG. 1 is an explanatory view useful for understanding a principle of a movement tracking processing by a correlation arithmetic operation.
A search image, which is derived through an image sensor 11 equipped with a television camera and a video camera, is converted by an A/D converter 12 into a search image represented by digital data, and then stored in a search image memory 13. On the other hand, a reference image memory 14 stores therein a reference image which is set up fixedly beforehand or cut out from a past search image.
The search image and the reference image are read out from the search image memory 13 and the reference image memory 14, respectively, in accordance with address information generated from an address generator 15, and then transferred to a correlation arithmetic unit 16. In the correlation arithmetic unit 16, a correlation arithmetic operation, which will be described later, is performed, so that correlation values associated pixels of the search image thus obtained are fed to a correlation value peak position detector 17 to detect a peak position of the correlation value. The peak position has an identical or similar to the pattern of the reference image on the search image. The peak position detected by the correlation value peak position detector 17 is outputted to the exterior in form of information representative of a position of a moving object on the search image at the present time, and is fed back to the address generator 15. That is, the peak position detected by the correlation value peak position detector 17 is transmitted to the address generator 15 so that a search can be performed on a certain area taking the peak position (the position of the moving object on the search image at the present time point) detected at the present time, when the position of the moving object on the search image at the subsequent time is searched.
FIG. 2 is a view representative of a pixel division of a reference image. FIG. 3 is a view showing an example of a pattern on the reference image. FIG. 4 is a view representative of a pixel division of a search image. FIG. 5 is a view showing an example of a pattern on the search image. FIG. 6 is an explanatory view useful for understanding a correlation arithmetic processing between the reference image and the search image. FIG. 7 is a typical illustration showing a distribution of correlation values.
Here, for the purpose of simplification, it is assumed that the reference image is of 8xc3x978 pixels as shown in FIG. 2, and a pixel value of a pixel of coordinates (i, j) is expressed by X (i, j). In a similar fashion to this, it is assumed that the search image is of 16xc3x9716 pixels as shown in FIG. 4, and a pixel value of a pixel of coordinates (i, j) is expressed by Y (i, j).
Here, as shown in FIG. 6, a partial area image (here, typically, a partial area image area taking coordinates (m, n) as the center) of the same size as the reference image is cut out from the search image, and the correlation value D (m, n) is computed in accordance with the following formula (1).                               D          ⁡                      (                          m              ,              n                        )                          =                                            ∑                              i                =                0                            7                        ⁢                                          ∑                                  j                  =                  0                                7                            ⁢                              {                                                      Y                    ⁡                                          (                                                                        m                          +                          i                                                ,                                                  n                          +                          j                                                                    )                                                        xc3x97                                      X                    ⁡                                          (                                              i                        ,                        j                                            )                                                                      }                                                                                                          ∑                                      i                    =                    0                                    7                                ⁢                                                      ∑                                          j                      =                      0                                        7                                    ⁢                                                            (                                              X                        ⁡                                                  (                                                      i                            ,                            j                                                    )                                                                    )                                        2                                                                        ⁢                                                            ∑                                      i                    =                    0                                    7                                ⁢                                                      ∑                                          j                      =                      0                                        7                                    ⁢                                                            (                                              Y                        ⁡                                                  (                                                                                    m                              +                              i                                                        ,                                                          n                              +                              j                                                                                )                                                                    )                                        2                                                                                                          (        1        )            
where the denominator of the formula (1), that is, the parts set forth below are quantities referred to as norm of the reference image and norm of the search image, respectively.                     ∑                  i          =          0                7            ⁢                        ∑                      j            =            0                    7                ⁢                              (                          X              ⁡                              (                                  i                  ,                  j                                )                                      )                    2                      ,                    ∑                  i          =          0                7            ⁢                        ∑                      j            =            0                    7                ⁢                              (                          Y              ⁡                              (                                                      m                    +                    i                                    ,                                      n                    +                    j                                                  )                                      )                    2                    
This arithmetic operation is sequentially performed while m and n are altered in the range of m=0 to 7, and n=0 to 7, respectively, as shown in FIG. 6. Thus, a distribution of the correlation values as shown in FIG. 7 is determined. Detection of the peak position of the correlation values makes it possible to detect a position wherein a pattern, which is identical or similar to the pattern (cf. FIG. 3 for example) of the reference image, exists on the search image (cf. FIG. 5 for example).
The formula (1) is representative of a correlation arithmetic operation referred to as a so-called normalized correlation. According to the conventional technology, however, there is a need to prepare a very large scale circuit to execute the normalized correlation arithmetic operation.
In view of the foregoing, Japanese Patent Laid Open Gazettes Hei. 5-114028 and Hei. 5-189570 disclose a technology of reducing a scale of a circuit for performing the normalized correlation arithmetic operation. The technology disclosed the above-referenced Gazettes is to compress a two-dimensional image to a one-dimensional image through producing a projection histogram or addition of intensity values to an x-direction or a y-direction, so that an arithmetic operation for the normalized correlation is performed on the one-dimensional image. Thus, it is possible to greatly reduce a circuit scale since it is sufficient that the normalized correlation is performed on the one-dimensional image. However, there is a possibility that information is dropped in the process in which two-dimensional image is compressed to the one-dimensional image, and thus there is a possibility that accuracy of a position detection of a moving object is lowered.
Further, there is known a so-called SAD(Sum of Absolute Difference), instead of the normalized correlation of the formula (1), in which the correlation arithmetic operation is performed in accordance with the following formula (2).                               D          ⁡                      (                          m              ,              n                        )                          =                              ∑                          i              =              0                        7                    ⁢                                    ∑                              j                =                0                            7                        ⁢                          "LeftBracketingBar"                                                Y                  ⁡                                      (                                                                  m                        +                        i                                            ,                                              n                        +                        j                                                              )                                                  -                                  X                  ⁡                                      (                                          i                      ,                      j                                        )                                                              "RightBracketingBar"                                                          (        2        )            
where m=0xcx9c7, n=0xcx9c7
As a circuit for performing the SAD, it is possible to use a circuit which is greatly smaller in a circuit scale as compared with a circuit for performing the normalized correlation.
In case of the SAD, when the pattern of the search image is completely coincident with the pattern of the reference image, there is obtained D(m, n)=0. Thus, a position of the minimum peak value of D(m, n) obtained through the formula (2) is detected.
However, the SAD brings about great degradation in arithmetic accuracy when luminance of the search image is varied (for example, the moving object enters the shade), and thus in general the SAD involves a problem that it is greatly poor in a position detection ability for the moving object as compared with the normalized correlation. Accordingly, it is restricted to an especial case such as under condition that luminance of the search image is constant that accuracy of the same degree as the normalized correlation is ensured.
In view of the foregoing, it is an object of the present invention to provide an image processing unit capable of performing a normalized correlation maintaining a two-dimensional image with a smaller circuit scale as compared with the conventional one.
To achieve the above-mentioned objects, the present invention provides an image processing unit for performing an arithmetic operation between a reference image and a search image, upon receipt of the reference image and the search image, said image processing unit having an image processing section comprising:
a first multiplication section for computing a square of a pixel value of the reference image;
an addition section for adding square value of the pixel values of the reference image obtained by said first multiplication section over a plurality of pixels;
a first square root computing section for computing a square root of an additional value over a plurality of pixels of the square value of the pixel values of the reference image obtained by said addition section to determine a norm of the reference image;
a product-sum operation section used on a common basis for both an addition of square values of pixel values of the search image over a plurality of pixels and an addition of multiplication values of pixel values of pixels associated with the search image and the reference image over a plurality of pixels;
a second square root computing section for computing a square root of an additional value over a plurality of pixels of the square value of the pixel values of the search image obtained by said product-sum operation section to determine a norm of the search image;
a second multiplication section for multiplying the norm of the reference image obtained by said first square root computing section and the norm of the search image obtained by said second square root computing section together; and
a division section for dividing an additional value of multiplication values of pixel values of pixels associated with the search image and the reference image over a plurality of pixels obtained by said product-sum operation section by a multiplication value between the norm of the reference image and the norm of the search image obtained by said second multiplication section to obtain a normalization correlation value.
According to the image processing unit of the present invention as mentioned above, the product-sum operation section is used on a common basis for an operation for the addition of a square of a pixel value of a search image over a plurality of pixels and an operation for the addition of a multiplication of pixel values of pixels associated with the search image and the reference image over a plurality of pixels. An operation for a norm of the reference image is performed on a path (a path including a first multiplication section, an addition section and a first square root computing section) which is different from that of the product-sum operation section. Thus, according to the image processing unit of the present invention, it is possible to reduce the scale of a circuit and to perform the operation processing in form of the two-dimensional image.
In the image processing unit according to the present invention as mentioned above, it is preferable that said first multiplication section and said second multiplication section are used on a common basis by a single multiplication section. Alternatively, it is preferable that said first square root computing section and said second square root computing section are used on a common basis by a single square root computing section.
A circuit arrangement, in which the multiplication section or the square root computing section is used on a common basis, makes it possible to more reduce the circuit scale.
In the image processing unit according to the present invention as mentioned above, it is preferable that said product-sum operation section has a mode in which instead of the addition of multiplication values of pixel values of pixels associated with the search image and the reference image over a plurality of pixels, an addition of absolute values of differences between pixel values of pixels associated with the search image and the reference image over a plurality of pixels is performed.
The adoption of the modes as mentioned above makes it possible to perform the SAD correlation as well as the normalization correlation using the image processing unit of the present invention.
In the image processing unit according to the present invention as mentioned above, it is preferable that said division section has a mode in which instead of a division by a multiplication value between the norm of the reference image and the norm of the search image obtained, a division is performed by a predetermined constant.
In this case, it is also preferable that said image processing section further comprises an absolute value computing section for computing an absolute value of a value obtained by said division section.
The numerator of the above-mentioned formula (1) represents a spatial filtering operation when a filter operator is adopted as a reference image.
Thus, in the event that the division section has the mode concerning with the division by a predetermined constant value, it is possible to perform the spatial filtering operation expressed by the following formula (3).                               D          ⁡                      (                          m              ,              n                        )                          =                                            ∑                              i                =                0                            7                        ⁢                                          ∑                                  j                  =                  0                                7                            ⁢                              {                                                      Y                    ⁡                                          (                                                                        m                          +                          i                                                ,                                                  n                          +                          j                                                                    )                                                        xc3x97                                      X                    ⁡                                          (                                              i                        ,                        j                                            )                                                                      }                                              C                                    (        3        )            
where m=0xcx9c7, n=0xcx9c7, and C is constant
Alternatively, in the event that a function as a spatial filter is provided even if a division is performed by the constant value, it is acceptable that the division section is bypassed.
An adoption of the absolute value computing section makes it possible to cope with the spatial filtering operation involving the absolute value operation, for example, a spatial filtering operation using the Sobel operator.
In the image processing unit according to the present invention as mentioned above, it is preferable that said image processing section further comprises a peak detection section for detecting a peak position on the search image as to the normalization correlation value obtained by said division section.
The image processing unit according to the present invention is basically an apparatus for performing a correlation operation, and thus it is acceptable that a peak detection of a correlation value is performed outside the apparatus as occasion demands. Alternatively, it is also acceptable that as mentioned above, a peak detection section is incorporated so that a peak position of a correlation value is detected within the image processing unit.
In the image processing unit as mentioned above, it is preferable that said product-sum operation section has a mode in which instead of the addition of multiplication values of pixel values of pixels associated with the search image and the reference image over a plurality of pixels, an addition of absolute values of differences between pixel values of pixels associated with the search image and the reference image over a plurality of pixels is performed, and
said peak detection section detects a peak position on the search image as to the addition of absolute values in said mode.
This feature makes it possible to detect the peak position through performing the SAD correlation.
In the image processing unit according to the present invention as mentioned above, it is preferable that said product-sum operation section has a systoric array for performing an operation between all of a plurality of bits representative of one pixel value when pixel values are expressed by a plurality of bits, and a part of bits belonging to one group when a plurality of bits representative of another pixel value is divided into a plurality of groups, and said systoric array assembles an operation result between said one pixel value and said another pixel value in accordance with a plurality of operation results obtained through a sequential operation on said plurality of groups.
Hitherto, there is known a systoric array as a suitable circuit structure for performing the product-sum operation. However, as mentioned above, when there is provided such an arrangement that an arithmetic operation between one pixel value and another pixel is divided into a plurality of partial arithmetic operations and is performed, so that a plurality of partial operation results are combined, it is possible to greatly reduce a circuit scale of the systoric array.
Further, in the image processing unit according to the present invention as mentioned above, it is preferable that said image processing section further comprises:
a first fixed-point achieving processing section for providing such a processing that when the additional value of the square value of the pixel values of the reference image over a plurality of pixels, which are obtained by said addition section, is such a small value that zeros are put at an upper significant bit end of a plurality of bits representative of the additional value, the additional value represented by the plurality of bits is shifted to the upper significant bit end so that a decimal point position is shifted to the upper significant bit end to transfer the same to said first square root computing section;
a second fixed-point achieving processing section for providing such a processing that when the additional value of the square value of the pixel values of the search image over a plurality of pixels, which are obtained by said product-sum operation section, is such a small value that zeros are put at an upper significant bit end of a plurality of bits representative of the additional value, the additional value represented by the plurality of bits is shifted to the upper significant bit end so that a decimal point position is shifted to the upper significant bit end to transfer the same to said second square root computing section; and
a third fixed-point achieving processing section for providing such a processing that the additional value of multiplication values of pixel values of pixels associated with the search image and the reference image over a plurality of pixels, which are obtained by said product-sum operation section, said additional value being expressed by a plurality of bits, is shifted to the upper significant bit end by a shift amount according to a shift amount in said first fixed-point achieving processing section and a shift amount in said second fixed-point achieving processing section so that a decimal point position is shifted to the upper significant bit end to transfer the same to said division section.
Provision of the first fixed-point achieving processing section, the second fixed-point achieving processing section and the third fixed-point achieving processing section makes it possible to perform a division with greater accuracy when a division between the smaller values is performed.
In the event that there is obtained such a small value that there is a possibility that even provision of the first fixed-point achieving processing section, the second fixed-point achieving processing section and the third fixed-point achieving processing section brings about a great degradation in accuracy of the division, it is acceptable that an alarm is issued.
In the image processing unit according to the present invention as mentioned above, it is preferable that said image processing section repeats by a plurality of number of times a partial operation according to a part of data of data representative of the reference image and the search image so that an operation according to the reference image and the search image are completed,
and wherein said image processing section further comprises:
a cache memory for storing the search image; and
a memory control section for providing such a control that while data representative of the search image is stored in said cache memory, data necessary for a partial operation for the first time of data representative of the search image is transferred to said image processing section, and with respect to two or more partial operations based on the same search image, necessary data is read from said cache memory to transfer the same to said image processing section.
In the event that the cache memory is provided, and with respect to two or more partial operations, necessary data is read from said cache memory, it is possible to reduce an idle time between the partial operations and thereby implementing a high speed processing.
In the image processing unit according to the present invention as mentioned above, it is preferable that said image processing unit further comprises a image memory having a plurality of frame memories each for storing a frame of search image, and a memory control section for providing such a control that the plurality of frame memories are used on a circulation basis so that an entered search image is stored in each of the frame memories one frame by one frame.
This feature makes it possible to always utilize the newest plurality of frame of search image. For example, with respect to a mobile object fast in movement, a mobile object, which appears on a search image immediately before the present search image, is derived to be a reference image. On the other hand, with respect to a mobile object slow in movement, a mobile object, which appears on the previous search image far from the present search image by a plurality of frames, is derived to be a reference image. A correlation operation is performed between the reference image thus obtained and the present search image. This feature makes it possible to determine a mobile vector of the mobile object with greater accuracy, even if it is concerned with a system in which both the mobile object fast in movement and the mobile object slow in movement simultaneously exist.
Further, in the image processing unit according to the present invention as mentioned above, it is preferable that said image processing section comprises an operation command storage section for sequentially storing a plurality of operation commands, and an operation result storage section for sequentially storing a plurality of operation results, and said image processing section derives the operation command from said operation command storage section to perform an arithmetic operation in accordance with the operation command and causes a result of the arithmetic operation to be stored in said operation result storage section,
said image processing unit further comprises an image processing control section having two modes of a first mode in which the operation command is fed to said image processing section so as to be stored in said operation command storage section, and a second mode in which the operation result stored in said operation result storage section is derived, and
said image processing control section changes over from the first mode to the second mode when said operation result storage section is full, and changes over from the second mode to the first mode when said operation command storage section is empty.
This feature makes it possible to avoid the deadlock (a state that the transfer of the operation command and the operation result between the image processing section and the image processing control section cannot be performed) between the image processing section and the image processing control section, and thereby implementing a smooth transfer of the operation command and the operation result.